// 2021华为机试.叠积木 https://www.nowcoder.com/discuss/663327
// 自己写，没通过
//积木宽高相等，长度不等，每层只能放一个或拼接多个积木，每层长度相等，求最大层数，最少2层。
//输入：给定积木的长度，以空格分隔，例如:3 6 6 3。
//输出：如果可以搭建，返回最大层数，如果不可以返回-1。
//输入：3 6 6 3
//输出：3
//输入：3 5
//输出：-1
//分析：设所有积木长度总和为 sum ，若可以搭建为 m 层，每层积木长度为 n ，则必有
// sum = mn 设积木中长度最大值为 L1 ，则必有 n >= L1 本题只需求出积木总长度 sum
//， 找出其所有大于 L1 小于 sum 的因数，分别判断以此为每层长度能否成功搭建，
//如果可以，记录层数，最终找到最大的层数.在找每一层所要用的积木时，使用贪心策略，从大的积木开始判断
// 积木最长 L1, L2....
// 共m层 x n宽 = sum
// m ------------
// . ------- ----
// 1 ---- -------
// 0 --------- --

#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif

// not used
bool isMatchWidth(vector<int>& path, size_t width) {
  if (path.size() == 0) {
    return false;
  }
  size_t nSum = 0;
  for (auto n : path) {
    nSum += n;
    if (nSum > width) {
      return false;
    }
  }
  return nSum == width;
}

// sum
int judgeBuild(const vector<int>& vtAllBrick, vector<int>& vtUsed,
               vector<int>& path, int curWidth, vector<vector<int>>& ans) {
  //    PF("cur.w=%d, \n", curWidth);
  if (curWidth < 0) {
    return -1;
  }
  if (curWidth == 0) {
    ans.push_back(path);
    for (auto p : path) PF("%d,", p);
    PF("\n");
    PF("ans.adddddddddddddddddddddddd %d\n", ans.size());
    return curWidth;
  }
  for (size_t i = 0; i < vtUsed.size(); i++) {
    if (vtUsed[i]) {
      continue;
    }
    if (curWidth - vtAllBrick[i] >= 0) {
      vtUsed[i] = 1;
      // PF("try=%d/ cur.w=%d\n", vtAllBrick[i], vtAllBrick[i]);
      path.push_back(vtAllBrick[i]);
      judgeBuild(vtAllBrick, vtUsed, path, curWidth - vtAllBrick[i], ans);
      path.pop_back();
      vtUsed[i] = 0;
    }
  }
  return curWidth;
}

int getMaxLevel(vector<int> vtAllBrick) {
  if (vtAllBrick.size() < 2) {
    return -1;
  }
  std::sort(vtAllBrick.begin(), vtAllBrick.end(),
            [](int a, int b) { return a > b; });
  size_t nSum = 0;
  for (auto a : vtAllBrick) nSum += a;
  size_t nMax = 0;
  // 最少2层, 层宽width
  for (size_t width = vtAllBrick[0]; width <= nSum / 2; width++) {
    if (nSum % width > 0) {
      continue;
    }
    vector<int> vtUsed(vtAllBrick.size());
    vector<vector<int>> ans;
    vector<int> path;
    PF("judge---------------------------------------%d width=%d, sum=%d\n",
       ans.size(), width, nSum);
    judgeBuild(vtAllBrick, vtUsed, path, width, ans);
    PF("----------------%d, %d, %d\n", ans.size(), width, nSum);
    for (auto path : ans) {
      for (auto n : path) {
        PF("%d,", n);
      }
      PF("\n");
    }
    PF("\n");
    if (ans.size() * width == nSum) {
      PF("----------------%d\n", ans.size());
      nMax = std::max(ans.size(), nMax);
    }
  }
  return nMax;
}

// int main() {
//    vector<int> vtAllBrick = {3,6,6,3};
//    int n = getMaxLevel(vtAllBrick);
//    printf("%d\n", n);
//    return 0;
//}
